package com.wzy.leecode.linked;

/**
 * @Auther: wzy
 * @Date: 2021/12/06/20:49
 * @Description:
 */
public class LinkedUtils {
    /**
     * 添加节点
     *
     * @param head 头节点
     * @param add  新添加的节点
     */
    public static void add(Node head, Node add) {
        if (head == null)
            return;
        while (head.next != null) {
            head = head.next;
        }
        head.next = add;
    }

    /**
     * 顺序打印
     *
     * @param head 头节点
     */
    public static void print(Node head) {
        if (head == null) {
            System.out.println("链表是空的");
        }
        while (head != null) {
            System.out.print(head.value + " ");
            head = head.next;
        }
    }

    public static Node reverseKGroup(Node head, int k) {
        if (head == null || head.next == null || k <= 1) {
            return head;
        }
        Node dummyNode = new Node(0);
        dummyNode.next = head;
        Node curr = dummyNode.next;
        int count = 1;
        int num = 0;
        Node real = null;
        Node prev = null;
        while (curr != null) {
            count++;
            curr = curr.next;
            if (count == k) {
                num++;
                if (curr == null){
                    continue;
                }
                curr = curr.next;
                Node next = curr;
                Node n1 = dummyNode.next;
                Node n2 = n1.next;
                while (n2 != next) {
                    n1.next = n2.next;
                    n2.next = dummyNode.next;
                    dummyNode.next = n2;
                    n2 = n1.next;
                }
                if (num == 1) {
                    real = dummyNode.next;
                } else {
                    prev.next = dummyNode.next;
                }
                count = 1;
                // 保存上一次遍历的尾节点
                prev = n1;
                dummyNode.next = n2;
            }
        }
        return real;
    }

    /**
     * 原地
     *
     * @param head
     * @return
     */
    public static Node reverse1(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node dummyNode = new Node(0);
        dummyNode.next = head;
        Node prev = head;
        Node pCur = head.next;
        while (pCur != null) {
            prev.next = pCur.next;
            pCur.next = dummyNode.next;
            dummyNode.next = pCur;
            pCur = prev.next;
        }
        return dummyNode.next;
    }

    /**
     * @param head
     * @return
     */
    public static Node reverse(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node next = head.next;
        head.next = null;
        while (next != null) {
            Node n3 = next.next;
            next.next = head;
            head = next;
            next = n3;
        }
        return head;
    }

    /**
     * 递归实现单链表反转
     *
     * @param list 为传入的单链表
     */
    public static Node recursiveList(Node list) {
        // 如果链表为空 或者 链表中只有一个节点,直接返回
        // 也是递归结束的条件
        if (list == null || list.next == null)
            return list;
        Node recursive = recursiveList(list.next);
        // 将 list.next.next 指针指向当前链表 list
        list.next.next = list;
        // 将 list.next 指针指向 null
        list.next = null;
        // 返回反转之后的链表 recursive
        return recursive;
    }
    public static Node partition(Node head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        Node dummyNode = new Node(0);
        dummyNode.next = head;
        Node prev = dummyNode;
        while (prev.next != null){
            if (prev.next.value >= x){
                prev = prev.next;
                continue;
            }
            Node cur = prev.next;
            prev.next = prev.next.next;
            cur.next = dummyNode.next;
            dummyNode.next = cur;
            prev = prev.next;
        }
        return  dummyNode.next;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        for (int i = 2; i < 9; i++) {
            add(head, new Node(i));
        }
        Node node = partition(head, 4);
        print(node);
    }
}
